\documentclass[final]{elsarticle}

\usepackage[utf8]{inputenc} % These source files are coded in UTF-8.
\usepackage[english]{babel} % In order to use, for example, "\foreignlanguage".
\usepackage{fullpage}

\usepackage[normalem]{ulem}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\usepackage{subfigure,epsfig,color}
\usepackage{colortbl}
\usepackage{tikz}
\usetikzlibrary{mindmap}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}

\newcommand{\yields}{\Rightarrow}
\newcommand{\dimension}{\mbox{\rm dim}}
\tikzstyle{vertex}=[circle,minimum size=7.50pt]

\begin{document}

\title{A general cut-generating procedure for the stable set polytope\footnote{This work has been partially supported by the Stic/AmSud joint program by CAPES (Brazil), CNRS and MAE (France), CONICYT (Chile) and MINCYT (Argentina) --project 13STIC-05-- and the Pronem program by FUNCAP/CNPq (Brazil) --project ParGO.}}

\author[ufcdc]{Ricardo C. Corr\^{e}a}
\ead{correa@lia.ufc.br}
\author[sarmiento]{Diego Delle Donne}
\ead{ddelledo@ungs.edu.ar}
\author[sarmiento]{Ivo Koch}
\ead{ikoch@ungs.edu.ar}
\author[sarmiento]{Javier Marenco\corref{cor1}}
\ead{jmarenco@ungs.edu.ar}

\address[ufcdc]{Universidade Federal do Cear\'a,
Departamento de Computa\c ao,
Campus do Pici, Bloco 910,
60440-554 Fortaleza - CE, Brazil}
\address[sarmiento]{Universidad Nacional de General Sarmiento,
Instituto de Ciencias,
J. M. Guti\'errez 1150, Malvinas Argentinas, (1613) Buenos Aires,
Argentina}

% \cortext[cnpq]{Partially supported by CNPq, Brazil.}
% \cortext[cor1]{Corresponding author.}

\begin{abstract}
We propose a general procedure for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Camp\^{e}lo. In contrast to existing cut-generating procedures, our algorithm generates both rank and non-rank valid inequalities, hence it is of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.
\end{abstract}

\maketitle

\section{Introduction}

Let $G = (V, E)$ be an undirected graph with node set $V$ and edge set $E$. A \emph{stable set} in $G$ is a subset of pairwise non-adjacent vertices of $G$. Given a graph $G$, the \emph{maximum cardinality stable set problem} (MSS) asks for a stable set $S$ in $G$ of maximum cardinality. The {\em stability number of $G$} is the cardinality of $S$ and is denoted by $\alpha(G)$. MSS is NP-hard, and has been approached in the literature through several techniques. A number of exact methods have been developed to solve it, see \cite{Bomze99themaximum} for a survey.

Although combinatorial methods for MSS (like those in~\cite{Segundo.Losada.Jimenez.11, Tomita.Kameda.07}) perform better than branch and cut algorithms, it is of great interest to continue the search for efficient polyhedral methods for this problem. This is due to the facts that (a) MSS frequently appears as a sub-structure in many combinatorial optimization problems, (b) in many situations MSS is solved as a sub-routine for generating valid inequalities for general mixed integer programs (see, e.g., \cite{Atamturk200040}), and (c) real applications may need specific versions of MSS with additional constraints and in this context integer programming often turns out to be effective.

Mannino and Sassano~\cite{ManninoSassano96} introduced in 1996 the idea of edge projections as a specialization of Lov\'asz and Plummer's clique projection operation~\cite{LovaszPlummer86}. Many properties of edge projections are discussed in~\cite{ManninoSassano96} and, based on these properties, a procedure computing an upper bound for MSS is developed. This bound is then incorporated in a branch and bound scheme. Rossi and Smriglio take these ideas into an integer programming environment in~\cite{Rossi.Smriglio.01}, where a separation procedure based on edge projection is proposed. This procedure iteratively removes and projects edges with certain properties, and heuristically finds violated rank inequalities (i.e., inequalities of the form $\sum_{v\in A} x_v \leq \alpha(G[A])$, where $A\subseteq V$ and $G[A]$ is the subgraph of $G$ induced by $A$). Finally, Pardalos et al.~\cite{Pardalos} extend the theory of edge projection by explaining the facetness properties of the inequalities obtained by this procedure. The authors give a branch and cut algorithm that uses edge projections as a separation tool, as well as several known families of valid inequalities as the odd hole inequalities (with a polynomial-time exact separation algorithm), the clique inequalities (with heuristics), and mod-$\{2, 3, 5, 7\}$ cuts.

Edge projections are a special case of Lov\'asz and Plummer's clique projections~\cite{LovaszPlummer86}. Rossi and Smriglio propose in \cite{Rossi.Smriglio.01} to employ a sequence of edge projection operations to reduce the original graph $G$ and make it denser at the same time, allowing for a faster identification of clique inequalities on the reduced graph $G'$. A key step for achieving this is to be able to establish how $\alpha(G)$ is affected by these edge projections, or, in other words, how exactly $\alpha(G)$ relates to $\alpha(G')$. We aim at generalizing Rossi and Smriglio's procedure by projecting cliques instead of edges, so we also need to show how $\alpha(G)$ changes as a result of this operation. Our method allows thus to establish a more general relation between $G$ and $G'$.

In this article we propose the use of clique projections as a general method for cutting plane generation for the MSS, along with a new clique lifting procedure that leads to stronger inequalities than those obtained with the edge projection method. The proposed method is able to generate both rank and generalized rank valid inequalities (to be defined below), by resorting to the general lifting procedure introduced in~\cite{XavierCampelo11}. This approach allows to produce cuts of a quite general nature, including cuts from the known families of valid inequalities for the MSS polytope. This approach departs from the usual template-based paradigm for generating cuts, and seeks to unify and generalize the separation procedures for the known cuts. In this sense, our main goal is to provide a more complete understanding of the maximum stable set polytope, which may help also in the solution of other combinatorial optimization problems.

This work is organized as follows. In Section~II we define the MSS polytope $STAB(G)$  and state some useful properties. Section~III defines the operation of clique projection and explores some basic facts on this operation. In Sections~IV and V we introduce our cut-generating method, by applying the lifting method presented in~\cite{XavierCampelo11}. Finally, in Section~VI we present some preliminary computational experience on the DIMACS instances, which show that the method is competitive.

\section{The maximum stable set polytope}

Let $n := |V|$ and $\mathcal S(G)\subseteq\{0,1\}^n$ be the set of all characteristic vectors of
stable sets of $G$. We will write simply $\mathcal S$ when $G$ is clear from context. For $W \subseteq V$, $\mathcal S(G[W])$ stands for the characteristic vectors of stable sets of $G$ involving vertices in $W$ only. The polytope of stable sets of $G$ is denoted by
\[
STAB(G) = \mbox{conv} \{ x \mid x \in \mathcal S(G) \}.
\]
Note that the stability number of $G$ is $\alpha(G) = \max \{ \sum_{v \in V} x_v \mid x \in STAB(G) \}$. If $c \in \mathbb{R}^n$, then the {\em weighted stable number of $G$, according to $c$} is $\alpha(G, c) = \max \{ c^\top x \mid x \in STAB(G) \}$. The general form of a facet-inducing inequality of $STAB(G)$ is
\begin{equation}
c^\top x \leq \alpha(G[H], c),
\label{eq:ineq}
\end{equation}
where $c \in \mathbb{R}^n$, $c \geq \mathbf{0}$, and $H = \{ v \in V \mid c_v > 0 \}$. Note that if $c\in\{0,1\}^n$ then we have the rank inequality mentioned in the Introduction.

\xout{The following is an upper bound for the weighted stable set number based
on the unweighted one.}

\begin{lemma}
\xout{Let $c \in \mathbb{R}^n$, $c \geq \mathbf{0}$, and $c_{min} = \min \{ c_v
\mid v \in V, c_v > 0 \}$. If $\bar c \in \mathbb{R}^n$ is such that $\bar c_v = 0$, if $c_v = 0$, and $\bar c_v = c_v - c_{min}$, otherwise, then $\alpha(G, c) \leq c_{min} \alpha(G) + \alpha(G, \bar c)$.}
\label{lem:upalphac}
\end{lemma}

\begin{proof}
\xout{The weight of a stable set $S$ containing exactly $s$ nonnull weight
vertices can be written as}
\[
\text{\xout{$\sum_{v \in S} c_v = s c_{min} + \sum_{v \in S} (c_v - c_{min})
\leq s c_{min} + \alpha(G, \bar c).$}}
\]
\xout{The result follows from $s \leq \alpha(G)$.}
\end{proof}

\xout{Suppose we have a heuristic $H$ for computing $\alpha(G)$. With the help
of Lemma~\ref{lem:upalphac} we can obtain a simple heuristic for the weighted
maximum stable set problem  $\alpha(G, c)$ as follows. Subtract in step $j$ the minimum element $c_{{min}_{j-1}}$ from every coefficient of vector $\bar c_{j-1}$ ($\bar c_0 = c$), as in Lemma~\ref{lem:upalphac}. Perform this operation until (say after $k$ steps) the number of non null elements remaining in vector $\bar c_k$ allows for exact enumeration of  $\alpha(G, \bar c_k)$. Then an upper bound for $\alpha(G, c)$ is $\alpha(G) (\sum_{1 \leq j < k} c_{{min}_j} )+  \alpha(G, \bar c_k)$}

\xout{We present this lemma here since it will be useful for our clique-lifting
operation in Section~\ref{sec:clique-lift}. This operation involves the problem of finding an upper bound for the maximum weight of a stable set in a subgraph of $G$.}

{\color{red} Describe main known results on valid/facet-defining inequalities
following two approaches: (i) theoretical: special structures (clique, odd
holes, webs, etc), lifting techinques (Xavier \& Campelo and others); (ii)
algorithmic: separation techniques for special structures (clique, odd holes,
web); projection and rank inequalities; local cuts}

\section{Clique projection}

The edge projection operation as defined by Rossi and Smriglio involves the removal of vertices in the common neighborhood of the endpoints of the edge being projected, whereas the clique projection operation defined here does not remove these vertices. Due to this fact, the clique projection defined here does not correspond to the standard edge projection when the projected clique is an edge. The motivation for this variation in the definition will become clear in the remainder of this work. Define $N_W = \cap_{w \in W} N(w)$ and $N_{uv} = N(u) \cap N(v)$.

\begin{definition}[clique projection~\cite{LovaszPlummer86}]
Let $W \subseteq V$, $|W| \geq 2$, be a clique in $G$. The {\em clique projection} of $W$ gives the graph $G \mid W = (V, E \mid W)$ in which $E\mid W = E \cup \{ xy \not\in E \mid W \subseteq N(x) \cup N(y) \}$.
\end{definition}

The edges in $(E \mid W) \backslash E$ (i.e., the added edges after the projection) are called \emph{false edges}. If $W = \{ u, v \}$ for some $uv \in E$ and we remove the vertices in $N_{uv} \cup \{ u, v \}$ when performing the projection, we have the edge projection explored in~\cite{Pardalos,Rossi.Smriglio.01}. Indeed, in these works, the subgraph $\tilde G \mid \{ u, v \}[V \setminus (N_{uv} \cup \{ u, v \})]$ of the projected graph $\tilde G \mid \{ u, v \}$ is obtained from $\tilde G$ by removing $N_{uv} \cup \{ u, v \}$ and adding false edges $xy$ such that $yv \in E$ and $x \in U$, where $U \subseteq N(u)$ is such that $U \cup W$ induces a clique in $G$.

\begin{definition}[\cite{Rossi.Smriglio.01}]
An edge $uv \in E$ is {\em projectable} in $G$ if and only if there exists a maximum stable set $S$
in $G$ such that $S \cap \{u, v\} \ne \emptyset$.
\end{definition}

\begin{lemma}[\cite{ManninoSassano96}] 
If $uv \in E$ is a projectable edge in $G$, then $\alpha(G) = \alpha(H[V \setminus (N_{uv} \cup \{ u, v \})]) + 1$, where $H = G \mid \{ u, v \}$. \label{lem:edgeG1}
\end{lemma}

\begin{definition}
A clique $W \subseteq V$, $|W| \geq 2$, is {\em projectable} in $G$ if and only if there exists a maximum stable set $S$ in $G$ such that $S \cap W \ne \emptyset$.
\end{definition}

\begin{lemma} 
If a clique $W \subseteq V$, $|W| \geq 2$, is projectable in $G$, then $\alpha(G) = \alpha(H[V \setminus (N_W \cup W)])$ or $\alpha(G) = \alpha(H[V \setminus (N_W \cup W)]) + 1$, where $H = G \mid W$.
\label{lem:alphaproj}
\end{lemma}

\begin{proof}
$\alpha(H[V \setminus (N_W \cup W)]) \leq \alpha(G[V \setminus (N_W \cup W)])$ is a direct consequence of $E \subseteq E \mid W$. Thus, $\alpha(G)$ is an upper bound for $\alpha(H)$. On the other hand, $W$ being projectable and $E \mid W \subseteq E \mid \{ u, v \}$, for any edge $uv$ such that $u, v \in W$, imply $\alpha(H[V \setminus (N_W \cup W)]) \geq \alpha(G) - 1$ by Lemma~\ref{lem:edgeG1} (if $W$ is projectable, some edge $\{ u, v \} \subseteq W$ must be projectable too), giving the desired lower bound.
\end{proof}

Both cases of the above lemma may happen, as illustrated in the examples in Figure~\ref{fig:alphaproj}.

\begin{figure}[htb]
\centering
        \begin{subfigure}[{$\alpha(G) = 3$} and {$\alpha(H[V
        \setminus (N_W \cup W)]) = 2$}, where $H = G \mid W$.]{
			\input{decreasealpha.pdf_t}
			\label{fig:decrease}}
        \end{subfigure}%
        \qquad\qquad\qquad
        \begin{subfigure}[{$\alpha(G) = \alpha(H[V \setminus (N_W
        \cup W)]) = 3$}, where $H = G \mid W$.]{
			\input{equalalpha.pdf_t}
			\label{fig:equal}}
        \end{subfigure}%
\caption{Examples of the two cases of Lemma~\ref{lem:alphaproj} with $W = \{ f, g, h \}$. In~\subref{fig:notrank}, $\alpha(G) = \alpha(H[V \setminus (N_W \cup W)]) + 1$, whereas $\alpha(G) = \alpha(H[V \setminus (N_W \cup W)])$ in~\subref{fig:rank}, where $H = G \mid W$.}
\label{fig:alphaproj}
\end{figure}

\begin{corollary} 
\xout{If a clique $W \subseteq V$, $|W| \geq 2$, is projectable in $G$, then
$\alpha(G[V \setminus (N_W \cup W)]) = \alpha(H[V \setminus (N_W \cup W)])$ or
$\alpha(G[V \setminus (N_W \cup W)]) = \alpha(H[V\setminus (N_W \cup W)]) + 1$, where $H = G \mid W$.}
\label{coro:alphaproj}
\end{corollary}

\begin{proof}
\xout{The upper bound $\alpha(H[V \setminus (N_W \cup W)]) \leq \alpha(G[V
\setminus (N_W \cup W)])$ is a direct consequence of $E \subseteq E \mid W$.
For the lower bound, we use $\alpha(G[V \setminus
(N_W \cup W)]) \leq \alpha(G)$ and Lemma~\ref{lem:alphaproj} (since $W$ is
projectable) to write $\alpha(G[V \setminus
(N_W \cup W)]) \leq \alpha(H[V \setminus (N_W \cup W)]) + 1$.}
\end{proof}

{\color{red} state Lemma 2.3 of Rossi \& Smriglio as difference of edge to
clique projection; replace the graph in Figure~\ref{fig:alphaproj} by
Figure~\ref{newfig:alphaproj}; show projections of $\{ 0, 1, 2 \}$, $\{ 0, 1
\}$, and $\{ 0, 2, 3 \}$ as examples of all possible cases}

\begin{figure}[htb]
\centering
        \begin{subfigure}[{$\alpha(G) = 3$}.]{
			\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{extendedGraphExample}
			\end{tikzpicture}
			\label{newfig:decrease}}
        \end{subfigure}%
        \qquad\qquad\qquad
        \begin{subfigure}[{$W = \{ 0, 1, 2 \}$} and {$\alpha(G) = \alpha(H[V
        \setminus W]) = 3$}, where $H = G \mid W$.]{
			\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{extendedGraphExample}
			\path[-] 				(3) [style=dashed]	edge 	(5);
			\draw[style=dashed]		(3) to[out=90,in=-15] 		(8);
			\draw[style=dashed]		(4) to[out=150,in=45] 		(5);
			\end{tikzpicture}
			\label{newfig:equal}}
        \end{subfigure} \\
        \begin{subfigure}[{$W = \{ 0, 1 \}$} and {$\alpha(H[V
        \setminus (N_W \cup W)]) = 2$}, where $H = G \mid W$.]{
			\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{extendedGraphExample}
			\path[-] 				(3) [style=dashed]	edge 	(5);
			\draw[style=dashed]		(3) to[out=90,in=-15] 		(8);
			\draw[style=dashed]		(4) to[out=150,in=45] 		(5);
			\draw[style=dashed]		(4) to[out=135,in=5] 		(8);
			\end{tikzpicture}
			\label{newfig:decrease}}
        \end{subfigure}%
        \qquad\qquad\qquad
        \begin{subfigure}[{$W = \{ 0, 2, 3 \}$} and {$\alpha(H[V
        \setminus W]) = 2$}, where $H = G \mid W$.]{
			\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{extendedGraphExample}
			\draw[style=dashed]		(1) to[out=30,in=150] 		(4);
			\draw[style=dashed]		(1) to[out=335,in=205] 		(7);
			\draw[style=dashed]		(1) to[out=25,in=155] 		(6);
			\draw[style=dashed]		(5) to[out=335,in=205] 		(4);
			\draw[style=dashed]		(6) to[out=25,in=155] 		(4);
			\end{tikzpicture}
			\label{newfig:equal}}
        \end{subfigure}%\\
\caption{Examples of the two cases of Lemma~\ref{lem:alphaproj} with $W = \{ f, g, h \}$. In~\subref{fig:notrank}, $\alpha(G) = \alpha(H[V \setminus (N_W \cup W)]) + 1$, whereas $\alpha(G) = \alpha(H[V \setminus (N_W \cup W)])$ in~\subref{fig:rank}, where $H = G \mid W$.}
\label{newfig:alphaproj}
\end{figure}


\section{Clique-Lifting} \label{sec:clique-lift}

In this section we lay the basic facts for the cut-generating procedure for the MSS polytope. In particular, we are interested in applying the lifting procedure presented by Xavier and Camp\^{e}lo in~\cite{XavierCampelo11}, which is our main tool. We present this procedure and show how it can be applied in the particular MSS setting for the well-known clique inequalities.

We start with some preliminary definitions. Given a valid inequality
\begin{equation}
\sum_{v \in W} \pi_v x_v \leq \beta
\label{eq:validineq}
\end{equation}
for $STAB(G)$ with $W \subseteq V$, $\beta \in \mathbb{R}$, and $\pi_v \ne 0$ for all $v \in W$, we say that $W$ is the {\em support of~\eqref{eq:validineq}} and we denote by $F_W(\beta, \pi_{v \in W}) = \{ x \in STAB(G) \mid \sum_{v \in W} \pi_v x_v = \beta \}$ the face induced by $W$, $\beta$, and $\pi$, in $STAB(G)$.

\begin{lemma}[lifting lemma~\cite{XavierCampelo11}]
Let $U \subseteq V$, $\beta \in \mathbb{R}$ and $\pi_v \in \mathbb{R}$, for all $v \in U$, such that $\sum_{v \in U} \pi_v x_v \leq \beta$ is a valid inequality for $STAB(G)$. If $c^\top x - d \leq 0$, $c,x \in \mathbb{R}^n$ and $d \in \mathbb{R}$, is a valid inequality for $F_U(\beta, \pi_{v \in U})$, then
\begin{equation}
L_{x,\lambda}(U) = (c^\top x - d) - \lambda\left(\sum_{v \in U}
\pi_v x_v - \beta \right) \leq 0,
\label{eq:lifted}
\end{equation}
with 
\begin{equation}
\lambda \leq \min \left\{ \frac{c^\top x - d}{\sum_{v \in U}
\pi_v x_v - \beta} \mid x \in \mathcal S, \sum_{v \in U}
\pi_v x_v < \beta \right\},
\label{eq:lambda}
\end{equation}
is a valid inequality for $STAB(G)$.
\label{lem:lifting}
\end{lemma}

\begin{proof}
It is sufficient to show that~\eqref{eq:lifted} holds for any $x \in \mathcal
S$. If $x \in F_U(\beta, \pi_{v \in U})$, then $L_{x,\lambda}(U) \leq 0$ holds
because $c^\top x - d \leq 0$ is valid for $F_U(\beta, \pi_{v \in U})$.
Otherwise, $\sum_{v \in U} \pi_v x_v < \beta$ and, by definition,
\[
\lambda \leq \frac{c^\top x - d}{\sum_{v \in U}
\pi_v x_v - \beta}.
\]
Considering that $\sum_{v \in U} \pi_v x_v - \beta$ is negative, we get
\[
\lambda\left(\sum_{v \in U}
\pi_v x_v - \beta \right) \geq c^\top x - d.
\]
Thus, $L_{x,\lambda}(U) \leq 0$.
\end{proof}

A value $\lambda$ that satisfies~\eqref{eq:lambda} is said to be {\em valid} for a lifting of $c^\top x - d \leq 0$ with respect to $U$. Since $\lambda$ appears with a negative sign in~\eqref{eq:lifted}, it turns out that if $\lambda_1$ and $\lambda_2$ are valid and $\lambda_1 < \lambda_2$, then
\[
\left\{ x \not\in STAB(G) \mid L_{x,\lambda_1}(U) \leq 0 \right\} \subset
\left\{ x \not\in STAB(G) \mid L_{x,\lambda_2}(U) \leq 0 \right\}.
\]
Consequently, the greater the coefficient $\lambda$ is, the stronger the inequality~\eqref{eq:lifted} becomes. Sufficient conditions for~\eqref{eq:lifted} to be facet-defining for $STAB(G)$ are stated next.

\begin{theorem}[\cite{XavierCampelo11}]
If $F_U(\beta, \pi_{v \in U})$ is a facet of $STAB(G)$, $c^\top x \leq d$ is facet-defining for $F_U(\beta, \pi_{v \in U})$ and $\lambda$ satisfies~\eqref{eq:lambda} at equality, then~\eqref{eq:lifted} is facet-defining for $STAB(G)$.
\label{thm:liftfacet}
\end{theorem}

\begin{proof}
By definition, $\dimension(\{ x \in F_W(\beta, \pi_{v \in W}) \mid c^\top x = d \}) = \dimension(F_W(\beta, \pi_{v \in W})) - 1 = \dimension(STAB(G))-2$. Hence, there are $\dimension(F_W(\beta, \pi_{v \in W}))-1$ affine independent vectors in $\{ x \in F_W(\beta, \pi_{v \in W}) \mid c^\top x = d \}$. Such vectors are affine independent with a vector that gives $\lambda$, which shows that the face of $STAB(G)$ corresponding to~\eqref{eq:lifted} has dimension at least $\dimension(F_W(\beta, \pi_{v \in W})) = \dimension(STAB(G)-1)$.
\end{proof}

Define $\mathbf 1_{v \in W}$ as the binary size-$n$ vector $y$ such that $y[v] = 1$ if and only if $v \in W$. A special case of Lemma~\ref{lem:lifting} occurs when $U$ is a clique in $G$ such that $U = W \cup N_W$. In such a case, if $c^\top x - d \leq 0$ is a valid inequality for $F_{W \cup N_W}(1, \mathbf 1_{v \in W \cup N_W})$, then the application of the lifting operation~\eqref{eq:lifted}, for any valid $\lambda$, is called {\em clique-lifting of $c^\top x - d \leq 0$ with respect to $W$}. The following lemma establishes a sufficient condition for a clique-lifting operation to result in a valid inequality for $STAB(G)$.

\begin{lemma}
\xout{Let $W \subseteq V$, $|W| \geq 2$, be a clique in $G$ and $c^\top x - d
\leq 0$, $c,x \in \mathbb{R}^n$ and $d \in \mathbb{R}$, be a valid inequality
for $STAB(G \mid W)$. If $W$ contains a vertex $w$ such that $N(w) \setminus W$ is a clique in $G$, then $c^\top x - d \leq 0$ is also valid for $F_{W \cup N_W}(1, \mathbf 1_{v \in W \cup N_W})$.}
\label{lem:cliqueproj}
\end{lemma}

\begin{proof}
\xout{If $E \mid W = \emptyset$, then there is nothing to prove since $STAB(G
\mid W) = STAB(G)$ and $F_{W \cup N_W}(1, \mathbf 1_{v \in W \cup N_W}) \subseteq
STAB(G \mid W)$ in this case.
Otherwise, let $x \in F_{W \cup N_W}(1, \mathbf 1_{v \in W \cup N_W}) \cap
\mathcal S$ ($x$ is an integer point in $F_{W \cup N_W}(1, \mathbf 1_{v \in W
\cup N_W})$) and $uv$ be a false edge in $G \mid W$. By definition of $x$,
there exists $z \in W \cup N_W$ such that $x_z = 1$. We consider two cases to
show that $\{ uz, vz \} \cap E \neq \emptyset$. First, if $z \in W$, then the
claim holds because $W \subseteq N(u) \cup N(v)$ by definition of
clique-projection. Second, $z \in N_W$ and, by hypothesis, let $w \in W$
be such that $N(w) \setminus W$ is a clique in $G$. Since $\{ u, v \}
\cap N(w) \neq \emptyset$ (again because $W \subseteq N(u) \cup N(v)$),
the claim follows. We conclude that $x_u = 0$ or $x_v = 0$ and, consequently,
$x$ corresponds to a stable set of $G \mid W$, which means that $c^\top x - d
\leq 0$ holds. The lemma stems from the fact that $F_{W \cup N_W}(1, \mathbf
1_{v \in W \cup N_W})$ is a convex hull of the points in $F_{W \cup N_W}(1, \mathbf 1_{v \in W \cup N_W}) \cap \mathcal S$.}
\end{proof}

{\color{red}
\begin{lemma}
Let $W_1, \ldots, W_r$ be subsets of vertices such that $G_0 := G$ and, for
every $i \in \{ 1, \ldots, r \}$, $G_i$ stands for the projected graph $G_{i-1} \mid
W_i$. Also, let $c^\top x - d \leq 0$, $c,x \in \mathbb{R}^n$ and $d \in
\mathbb{R}$, be a valid inequality for $STAB(G_r)$.
Then,
\[
c^\top x + \sum_{t=1}^r \lambda_t (x_{W_t}
- 1) \leq d
\]
is valid for $STAB(G)$, where $P_t := \left\{ x \in STAB(G) \mid x_{W_t} = 0
\right\}$ and
\[
\lambda_t := \max \left\{ c^\top x + \sum_{i=t+1}^r \lambda_i (x_{W_i} - 1)
\mid x \in P_t \right\} - d
\]
\label{newlem:cliqueproj}
\end{lemma}

\begin{proof}
By induction on $t$.
\end{proof}}

\xout{A clique-lifting operation involves the problem of finding an upper bound
for the maximum weight of a stable set in a subgraph of $G$. The following lemma
establishes one such upper bound based on Lemma~\ref{lem:upalphac}.}

\begin{lemma}
\xout{Let $W \subseteq V$, $|W| \geq 2$, be a clique in $G$ and $c^\top x - d
\leq 0$, $c,x \in \mathbb{R}^n$ and $d \in \mathbb{R}$, be a valid inequality
for $STAB(G \mid W)$ with support $H$. Moreover, let $c_{min} = \min \{ c_v \mid v \in H \setminus (W \cup N_W), c_v > 0 \}$. If $W$ contains a vertex $w$ such that $N(w) \setminus W$ is a clique in $G$, then}
\begin{equation}
\text{\xout{$\lambda=d-c_{min}\alpha(G[H \setminus (W \cup N_W)])- \max_{x \in
\mathcal S(G[H \setminus (W \cup N_W)])} \sum_{v \in H \setminus (W \cup N_W)}
\max \{ 0, c_v - c_{min} \} x_v$}}
\label{eq:lemmalambda}
\end{equation}
\xout{is valid for the clique-lifting of $c^\top x - d \leq 0$ with respect to
$W$.}
\label{lem:aproxlambda}
\end{lemma}

\begin{proof}
\xout{Lemma~\ref{lem:lifting}, combined with Lemma~\ref{lem:cliqueproj},
establishes that $\lambda$ is valid for the clique-lifting of $c^\top x - d \leq 0$ with
respect to $W$ if}
\[
\begin{array}{rcl}
\text{\xout{$\lambda$}} & \text{\xout{$\leq$}} & \text{\xout{$\min \left\{
\frac{c^\top x - d}{\sum_{v \in W \cup N_W} x_v - 1} \mid x \in \mathcal S, \sum_{v \in W \cup N_W}
x_v = 0 \right\}$}} \\
& \text{\xout{$=$}} & \text{\xout{$\min \left\{ - c^\top x + d \mid x \in
\mathcal S(G[H\setminus (W \cup N_W)]) \right\}$}},
\end{array}
\]
\xout{where $H$ is the support of $c^\top x - d \leq 0$, which means that} 
\begin{equation}
\text{\xout{$\lambda \leq d - \max \left\{ c^\top x \mid x \in \mathcal S(G[H
\setminus (W \cup N_W)]) \right\}$}}.
\label{eq:lambdabound}
\end{equation}
\xout{Lemma~\ref{lem:upalphac} implies that the last two terms of the
righthand side of~\eqref{eq:lemmalambda} provide an upper bound for the
maximum weight of a stable set of $G[H \setminus (W \cup N_W)]$. Thus, the
result holds due to~\eqref{eq:lambdabound}.}
\end{proof}

The following result is a particular case of \xout{Lemma~\ref{lem:aproxlambda}}
Lemma~\ref{newlem:cliqueproj} and the basis of the separation procedure proposed in \cite{Rossi.Smriglio.01}.

\begin{corollary}\label{coro:aproxlambda}
If $W \subseteq V$ is projectable in $G[H \cup W \cup N_W]$ and $c^\top x - d \leq 0$ is the rank inequality for the subgraph of $G \mid W$ induced by $H \cup W \cup N_W$, then $\lambda=-1$ is valid for the clique-lifting of $c^\top x - d \leq 0$.
\end{corollary}

\begin{proof}
Using~\eqref{eq:lemmalambda} with $c_v = 1$, for all $v \in H \setminus (W
\cup N_W)$, and $\alpha(G[H \setminus (W \cup N_W)]) \leq \alpha(G \mid W[H
\setminus (W \cup N_W)])$.
\end{proof}

A remark in connection with this result is that $\alpha(G[H]) = \alpha(G \mid
W[H])$ implies that $\lambda = 0$ is valid for the clique-lifting of $c^\top x -
d \leq 0$. Such a situation is depicted in \xout{Figure~\ref{fig:sumrc}}
Figure~\ref{newfig:sumrc}.

\begin{figure}[htb]
\centering
        \begin{subfigure}[Graph $G = G^{(0)}$, $\alpha(G) = 3$. It generates the
        valid inequality $x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 \leq 3$, which is the summation of
        the rank inequality $x_3 + x_4 + x_5 + x_6 + x_7 \leq 2$ with
        the clique one $x_1 + x_2 \leq 1$.]{
			\input{sumrc1.pdf_t}
			\label{fig:sumrc1}}
        \end{subfigure}%
        \qquad
        \begin{subfigure}[Graph $G^{(1)}$, $\alpha(G^{(1)}) = 2$, after
        projecting edge $(1,2)$ containing one false edge ($(3,5)$). It generates the inequality $x_3
        + x_4 + x_5 + x_6 + x_7 \leq 2$, which is valid for $G$.]{
			\input{sumrc2.pdf_t}
			\label{fig:sumrc2}}
        \end{subfigure}%
        \qquad
        \begin{subfigure}[Graph $G^{(2)}$, $\alpha(G^{(2)}) = 1$, after
        projecting edge $(5,6)$ containing one false edge ($(4,7)$). It generates the inequality $x_3
        + x_4 + x_7 \leq 1$, which is not valid for $G^{(1)}$.]{
			\input{sumrc3.pdf_t}
			\label{fig:sumrc3}}
        \end{subfigure}%
\caption{Example of a sequence of edge projections such that the final lifted inequality is weaker than an intermediary one. Deleting false edges from $G^{(1)}$ does not increase the maximum size of a stable set.}
\label{fig:sumrc}
\end{figure}

\begin{figure}[htb]
\centering
        \begin{subfigure}[Graph $G = G_0$, $\alpha(G) = 3$.]{
			\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{graphExample}
			\end{tikzpicture}
			\label{newfig:sumrc1}}
        \end{subfigure}%
        \qquad
        \begin{subfigure}[Graph $G_1$, $\alpha(G_1) = 3$, after
        projecting clique $\{0,1,2\}$ containing two false edges. It
        generates the inequality $x_1 + x_5 + x_6 + x_7 + x_4 + 2x_0 +
        2x_2 + 2x_3 \leq 3$, which is valid for $G$ since to $\lambda_1 =
        0$.]{ 
        	\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{graphExample}
			\path[-] 				(3) [style=dashed]	edge 	(5);
			\draw[style=dashed]		(5) to[out=335,in=205] 		(4);
			\end{tikzpicture}
			\label{newfig:sumrc2}}
        \end{subfigure}%
        \qquad
        \begin{subfigure}[Graph $G_2$, $\alpha(G_2) = 2$, after
        projecting clique $\{ 0, 2, 3 \}$ containing several false edges.
        It generates the inequality $x_1 + x_5 + x_6 + x_7 + x_4 \leq 1$, which
        is not valid for $G_1$ due to $\lambda_2 = 2$.]{ 
        	\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{graphExample}
			\path[-] 				(3) [style=dashed]	edge 	(5);
			\draw[style=dashed]		(1) to[out=30,in=150] 		(4);
			\draw[style=dashed]		(1) to[out=335,in=205] 		(7);
			\draw[style=dashed]		(1) to[out=25,in=155] 		(6);
			\draw[style=dashed]		(5) to[out=335,in=205] 		(4);
			\draw[style=dashed]		(6) to[out=25,in=155] 		(4);
			\end{tikzpicture}
			\label{newfig:sumrc3}}
        \end{subfigure}%
        \qquad
        \begin{subfigure}[Graph $G_3$, $\alpha(G_3) = 2$, after
        projecting clique $\{ 0, 3, 4 \}$ containing one additional false edge.
        It generates the inequality $x_1 + x_5 + x_6 + x_7 + x_4 \leq 1$,
        which is valid for $G_2$ since $\lambda_3 = 0$.]{ 
        	\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{graphExample}
			\path[-] 				(3) [style=dashed]	edge 	(5);
			\path[-] 				(2) [style=dashed]	edge 	(7);
			\draw[style=dashed]		(1) to[out=30,in=150] 		(4);
			\draw[style=dashed]		(1) to[out=335,in=205] 		(7);
			\draw[style=dashed]		(1) to[out=25,in=155] 		(6);
			\draw[style=dashed]		(5) to[out=335,in=205] 		(4);
			\draw[style=dashed]		(6) to[out=25,in=155] 		(4);
			\end{tikzpicture}
			\label{newfig:sumrc3}}
        \end{subfigure}%
\caption{Example of a sequence of clique projections. Deleting false edges from
$G_1$ does not increase the maximum size of a stable set.}
\label{newfig:sumrc}
\end{figure}

{\color{red}
\section{Strengthened Clique-Lifting}

Let $W_1, \ldots, W_r$ be subsets of vertices such that $G_0 := G$ and, for
every $i \in \{ 1, \ldots, r \}$, $G_i$ stands for the projected graph $G_{i-1} \mid
W_i$.

$F_0 := STAB(G)$ and, for $t \in \{ 1, \ldots, r \}$,
\[
F_t = \{ x \in F_{t-1} \mid x_{W_t} = 1 \} = \{ x \in
STAB(G) \mid x_{W_j} = 1, j = 1, \ldots, t \}
\]

\begin{lemma}
$F_t \subseteq STAB(G_t)$, for all $t \in \{ 1, \ldots, r \}$
\end{lemma}

\begin{proof}
If $F_t = \emptyset$, then there is nothing to prove. Otherwise, we use
induction on $t$ to show that $F_t \cap \mathcal S \subseteq STAB(G_t) \cap
\mathcal S$. For $t = 1$, let $x \in F_1 \cap \mathcal S$ ($x$ is an integer
point in $F_1$) and $uv \in E_1$. By definition of $x$, there exists $z \in W_1$
such that $x_z = 1$. It follows that $\{ uz, vz \} \cap E \neq \emptyset$
because $W_1 \subseteq N(u) \cup N(v)$ by definition of clique projection. We conclude that $x_u = 0$ or $x_v = 0$ and, consequently,
$x$ corresponds to a stable set of $G_1$. For $t > 1$, $F_t \subseteq F_{t-1}$,
by definition, and $F_{t-1} \subseteq STAB(G_{t-1})$, by the induction
hypothesis. We show that $x \in (STAB(G_{t-1}) \setminus STAB(G_t)) \cap
\mathcal S$ implies $x \not\in F_t$. For such an $x$, there is $uv \in E_t$
such that $x_u = x_v = 1$. By definition of clique projection, $\{ uz, vz \}
\cap E[G_{t-1}] \neq \emptyset$ holds for every $z \in W_t$, leading to $x_{W_t}
= 0$.
\end{proof}

\begin{lemma}
$F_t = \{ x \in STAB(G_t) \mid x_{W_j} = 1, j = 1, \ldots, t \}$, for all
$t \in \{ 1, \ldots, r \}$
\end{lemma}

\begin{proof}
\begin{description}
\item[$F_t \supseteq \{ x \in STAB(G_t) \mid x_{W_j} = 1, j = 1,
\ldots, t \}$] Stems directly from $STAB(G_t) \subseteq STAB(G)$
\item[$F_t \subseteq \{ x \in STAB(G_t) \mid x_{W_j} = 1, j = 1,
\ldots, t \}$] Directly from the previous lemma
\end{description}
\end{proof}
Since $W_1, \ldots, W_t$ are cliques of $G_{t-1}$, $F_t$ is a face
of $STAB(G_{t-1})$.

\begin{lemma}
Let $c^\top x - d \leq 0$, $c,x \in \mathbb{R}^n$ and $d \in
\mathbb{R}$, be a valid inequality for $STAB(G_r)$.
Then,
\[
f_\ell(x) = c^\top x + \sum_{t=\ell+1}^r \lambda_t (x_{W_t} - 1) \leq d
\]
is valid for $STAB(G)$, where $\mathcal S_t = \mathcal S \cap \{ x \in STAB(G_t) \mid
x_{W_j} = 1, j = 1, \ldots, t \}$ and
\[
\lambda_t = \max \left\{ \{ 0 \} \cup \left\{ c^\top x + \sum_{i=t+1}^r
\lambda_i (x_{W_i} - 1) \mid \begin{array}{l} x \in \mathcal S_{t-1}, \\ x_{W_t} = 0 \end{array} \right\} \right\} - d
\]
\end{lemma}

\begin{proof}
By induction on $t$. For $t = r$, the results follows since $c^\top x -d \leq 0$
is valid for $STAB(G_r)$ and $F_r \subseteq STAB(G_r)$.
For $t < r$, by induction hypothesis, $f_{t+1}(x) \leq \pi_0$ is valid for
$F_{t+1} = \{ x \in F_t \mid x_{W_{t+1}} = 1 \}$. Applying the inequality
construction, we get $\lambda_{t+1} = 0$, if $\{ x \in \mathcal S_t \mid
x_{W_{t+1}} = 0 \} = \emptyset$, or
\[
\lambda_{t+1} = \max \left\{ c^\top x + \sum_{i=t+2}^r \lambda_i (x_{W_i} - 1)
\mid \begin{array}{l} x \in \mathcal S_t, \\ x_{W_{t+1}} = 0 \end{array} \right\} -
\pi_0
\]
By the Lifting Lemma (considering that $\mathcal S_t = \mathcal S \cap F_t$),
we obtain that $f_t(x) \leq \pi_0$ is valid for $F_t$.
\end{proof}

\begin{figure}[htb]
\centering
        \begin{subfigure}[Graph $G = G_0$, $\alpha(G) = 3$.]{
			\begin{tikzpicture}[thick,fill opacity=0.5,scale=0.4,font=\scriptsize]
			\input{graphExample}
			\path[-] 				(2) edge 	(7);
			\end{tikzpicture}}
        \end{subfigure}
\caption{Example of a sequence of strengthened clique projections.}
\end{figure}

\section{Sufficient Conditions for Faceteness}

There exists $k > 0$ such that:
\begin{itemize}
  \item $|W_t| = k$, for all $t \in \{ 1, \ldots, r \}$
  \item the subgraph of $G_r$ induced by $\bigcup_{t=1}^r W_t$ is $k$-partite
  with vertex classes $V_1, \ldots, V_k$
  \item for all $v \in V_0 = V \setminus \bigcup_{i=1}^k V_i$, there exists $i
  \in \{ 1, \ldots, k \}$ such that $N(v) \cap V_i = \emptyset$ (this implies
  that all cliques are maximal in $G_r$)
\end{itemize}

\begin{lemma}
$dim(F_t) = |V| - t$, for all $t \in \{ 1, \ldots, r \}$
\end{lemma}

\begin{proof}
\begin{description}
\item[$dim(F_t) \leq |V| - t$] By lemma $F_t = \{ x \in STAB(G_t) \mid x_{W_j} =
1, j = 1, \ldots, t \}$
\item[$dim(F_t) \geq |V| - t = |V_0| + k - 1$] Let $x^i$ be the incidence vector of $V_i$, $i \in \{ 1, \ldots, k \}$:
  \begin{itemize}
    \item $x^i \in STAB(G)$
    \item $x^i \in F_t$: $x^i_{W_j} = 0$, $1 \leq j \leq t$, 
    $\yields$ $\exists$ two vertices in $W_j \cap V_{\ell \ne i}$
    (pigeonhole principle) $\yields$ contradiction ($V_\ell$ is stable set of $G_t$)
  \end{itemize}
\end{description}

Let $y^v = x^i + e^v$, for $v \in V_0$, $i \in \{ 1, \ldots, k \}$, and $N(v)
\cap V_i = \emptyset$:
\begin{itemize}
  \item $y^v \in F_t$
  \item $\{ x^i \}^k_{i=1} \cup \{ y^v \}_{v \in V_0}$ are affinely
independent
\end{itemize}
\end{proof}

\begin{description}
\item[$\mathcal W_t$:] set of maximal cliques of $G_t$, for all $t \in \{ 0, 1,
\ldots, r-1 \}$
\item[$T = (V_T, \mathcal W_T)$:] $k$-uniform strong hypertree such that:
\begin{itemize}
  \item $\mathcal W_T = \{ W_1 \in \mathcal W_0, \ldots, W_r \in \mathcal
  W_{r-1} \}$
  \item $\langle W_1, \ldots, W_r \rangle$ is an ordering of $\mathcal W_T$ such
  that the hypergraph induced by $W_1, \ldots, W_t$ is a strong hypertree,
  $\forall t \leq r$
  \item the subgraph of $G_r$ induced by $V_T$ is $k$-partite with vertex
  classes $V_1, \ldots, V_k$
  \item no vertex in $V_0 := V \setminus V_T$ has neighbors in all classes
  $V_1, \ldots, V_k$
\end{itemize}
\end{description}

\begin{lemma}
If $x \in F_r$, then $x_u = x_v$, for all $u, v \in V_i$, $i
\in \{ 1, \ldots, k \}$
\label{lem:A}
\end{lemma}

\begin{proof}
Let $W_{t_1}, \ldots, W_{t_q}$ be the strong hyperpath in $T$ connecting $u,
v$. By induction on $q$:
\begin{description}
\item[$q = 2$] $x_{W_{t_1}} - x_{W_{t_2}} = x_u - x_v = 0$
\item[$q > 2$] Let $w \in W_{t_2} \setminus W_{t_1}$ and $p = \max \{ \ell \mid
w \in W_{t_\ell} \}$:
\begin{itemize}
  \item $w \in V_i$ and $W_{t_1}, W_{t_2}$ is a strong hyperpath with 2
  hyperedges connecting $u,w$ $\yields$ $x_u = x_w$
  \item $w \in V_i$ and $W_{t_p}, \ldots, W_{t_q}$ is a strong hyperpath with
  less than $q$ hyperedges connecting $w,v$ $\yields$ $x_w = x_v$
\end{itemize}
\end{description}
\end{proof}

}

\section{The cut-separating procedure}

Successive applications of the clique projection operation and the corresponding clique-lifting operations according to Lemma~\ref{lem:cliqueproj}, lead to stronger inequalities than those that can be obtained with the edge projection method proposed in~\cite{Rossi.Smriglio.01}. In fact, the edge projection corresponds to a special case of Lemma~\ref{lem:cliqueproj} in which inequality $c^\top x - d \leq 0$ is a rank inequality of a projected graph's clique with empty intersection with $W$. As an illustration, consider the structure in Figure~\ref{fig:notrank} and $W = \{ d, e, f \}$. The $de$ projection in this graph, followed by the antiprojection of the clique $\{ a, b, c \}$ of $G \mid de$, gives the rank inequality $x_a + x_b + x_c + x_d + x_e + x_f \leq 2$. The same inequality is obtained with Lemma~\ref{lem:cliqueproj} if we take as $c^\top x - d \leq 0$ the clique inequality of $G + de$ for $\{ a, b, c \}$. Nevertheless, even in this simple example, there is an inequality that cannot be derived with the method in~\cite{Rossi.Smriglio.01}. If we take $\{ a, b, c, f \}$ as the clique inducing set of vertices associated with $c^\top x - d \leq 0$ in Lemma~\ref{lem:cliqueproj}, then we get $x_a + x_b + x_c + x_d + x_e + 2x_f \leq 2$ as a valid (indeed, facet-defining~\cite{Campelo.Campos.Correa.08}) inequality for $STAB(G)$.

\begin{figure}[htb]
\centering
        \begin{subfigure}[Not rank inequality.]{
			\input{separat.pdf_t}
			\label{fig:notrank}}
        \end{subfigure}%
        \qquad
        \begin{subfigure}[Rank inequality.]{
			\input{nomaximal.pdf_t}
			\label{fig:rank}}
        \end{subfigure}%
\caption{Structures leading to stronger inequalities than edge projection.}
\label{fig:graph}
\end{figure}

The structure in Figure~\ref{fig:rank} (assuming that it induces a rank inequality of $G$~\cite{Balas.Padberg.76,Campelo.Campos.Correa.08}) also illustrates the fact that $\sum_{v \in W} x_v \leq 1$ being facet-defining for $STAB(G)$ is not necessary to derive another facet of $STAB(G)$. To show this, we choose $W = \{ d, e \}$ and still take the clique inequality of $G + de$ associated with $\{ a, b, c, f \}$. With such a configuration, Lemma~\ref{lem:cliqueproj} gives the rank inequality $x_a + x_b + x_c + x_d + x_e + x_f \leq 2$ as well. Observe that this inequality is not derived by the method in~\cite{Rossi.Smriglio.01} if edge $ae$ is deleted before projecting $de$ ($x_b + x_c + x_d + x_e + x_f \leq 2$ would be generated instead).

% \begin{definition}[\cite{Rossi.Smriglio.01}]
% An edge $uv$ is {\em
% strongly projectable} in $G$ if it is projectable in every induced subgraph of $G$ containing both $u$ and $v$.
% \end{definition}
% 
% In~\cite{Rossi.Smriglio.01}, $N_{uv} \cup \{ u, v \}$ is a maximal clique
% containing a strongly projectable edge $uv$ of a relaxed graph $\tilde G$.

We are now in position of presenting the cut-generating procedure that is the main contribution of this work. Algorithm~\ref{alg:procedure} summarizes the proposed procedure: we generate and project a sequence of cliques until we find a violated clique inequality. At this point, we antiproject the cliques in reverse order and apply the Lemma~\ref{lem:lifting} in order to get a valid inequality for the original graph.

\begin{algorithm}
\caption{Cut-generating procedure}
\label{alg:procedure}
\begin{algorithmic}[1]
\State Find a starting clique $W^{(0)}$ of $G$;
\State $k := 0$;
\While {$x(W^{(k)}) \le 1$}
    \State Remove edges such that $N(w)\backslash W^{(k)}$ is a clique,
    \State for some $w\in W^{(k)}$;
    \State Project the clique $W^{(k)}$, getting the graph $G^{(k+1)}$;
    \State Find a clique $W^{(k+1)}$;
    \State $k := k+1$;
\EndWhile
\State Let $\pi^{(k)}$ be the characteristic vector of $W^{(k)}$
\State (so the inequality $\pi^{(k)} x\le \gamma^{(k)} := 1$ is violated);
\For {$i \gets k, \ldots, 1$}
    \State Apply Lemma~\ref{lem:aproxlambda} to $\pi^{(k)} x\le \gamma^{(k)}$ and $W^{(k)}$ in graph
    \State $G^{(k-1)}$, obtaining a new inequality $\pi^{(k-1)} x\le \gamma^{(k-1)}$
    \State valid for $G^{(k-1)}$;
\EndFor
\State \textbf{return} $\pi^{(0)} x\le \gamma^{(0)}$, if violated;
\end{algorithmic}
\end{algorithm}

Let $\langle W^{(0)}, \ldots, W^{(k)} \rangle$ be the sequence of $k \geq 0$ cliques $W^{(i)} \subseteq V$, $|W^{(i)}| \geq 2$, generated by the algorithm. Also, let $G^{(0)} = G, \ldots, G^{(k)}$ be the sequence of projected graphs within the algorithm. For $i \in \{ 0, \ldots, k \}$, there exists $w^{(i)} \in W^{(i)}$ and $R^{(i)}$ a minimal subset of $N_{G^{(i)}}(w^{(i)})$ such that $N_{G^{(i)}}(w^{(i)}) \setminus (W^{(i)} \cup R^{(i)})$ is a clique in $G^{(i)}$. Put differently, $R^{(i)}$ is a minimal subset of vertices such that the removal of all edges $w^{i}v$, $v \in R^{(i)}$, results in a graph $\tilde G^{(i)}$ in which $N_{\tilde G^{(i)}}(w^{(i)}) \setminus W^{(i)}$ is a clique. Observe that this is the sufficient condition stated in Lemma~\ref{lem:aproxlambda}. In addition, $W^{(i)}$ has the following property in $G^{(i)}$.

\begin{lemma} \label{lem:W-proj}
\xout{Let $W \subseteq V$, $|W| \geq 2$, be a clique in $G$. If there exists $w
\in W$ such that $N(w) \setminus W$ is a clique, then $W$ is projectable in
every subgraph of $G$ induced by $H \subseteq V$ such that $W \subseteq H$.}
\end{lemma}

\begin{proof}
\xout{Let $H \subseteq V$ such that $W \subseteq H$. If $S$ is a maximum stable
set of $G[H]$ and $S \cap W = \emptyset$, then $|S \cap N(w)| = 1$ since $N(w)
\setminus W$ is a clique. Thus, $S' = (S \setminus N(w)) \cup \{ w \}$ is a
maximum stable set of $G[H]$ such that $W \cap S' \ne \emptyset$.}
\end{proof}

Let us assume that $\bar x \not\in STAB(G^{(k)})$ be such that $\mathbf 1_{v \in W^{(i)}}^\top \bar x \leq 1$, for all $i \in \{ 0, \ldots, k-1 \}$, and $\mathbf 1_{v \in W^{(k)}}^\top \bar x > 1$. Applying Lemma~\ref{lem:cliqueproj} with $\lambda^{(k)}$ obtained with Lemma~\ref{lem:aproxlambda}, we obtain the inequality
\[
\mathbf 1_{v \in W^{(k-1)}}^\top x - 1 - \lambda^{(k)} (\mathbf 1_{v \in
W^{(k)}}^\top x - 1) \leq 0,
\]
valid for $STAB(G^{(k - 1)})$. If the subgraph of $G^{(k-1)}$ induced by $W^{(k)} \setminus (W^{(k-1)} \cup N_{W^{(k-1)}})$ does not increase its stability number with respect to $G^{(k)}$ (this happens if, for instance, $G^{(k)}$ has no false edges), then $\lambda^{(k)} = 0$ and $\mathbf 1_{v \in W^{(k)}}^\top x \leq 1$ is valid for $STAB(G^{(k-1)})$. Otherwise, by the definition of clique-projection, $\alpha(G^{(k-1)}[W^{(k)} \setminus (W^{(k-1)} \cup N_{W^{(k-1)}})]) = 2$ and $\lambda^{(k)} = -1$. Thus, the new inequality becomes
\[
\mathbf 1_{v \in W^{(k-1)} \oplus W^{(k)}}^\top x + \mathbf 2_{v \in
W^{(k-1)} \cap W^{(k)}}^\top x \leq 2,
\]
which is a rank inequality only if $W^{(k-1)} \cap W^{(k)} = \emptyset$. Since $\mathbf 1_{v \in W^{(k)}}^\top \bar x - 1 \leq 0$, this new inequality may be violated by $\bar x$.

Let us take Figure~\ref{fig:sumrc} as an example of a sequence of $k = 2$ clique-projections with the point $\bar x = \mathbf{1/2}_{v \in \{ 1, \ldots, 7 \}}$. The corresponding sequence of cliques is $W^{(0)} = \{ 1, 2 \}$ ($w^{(0)} = 2$), $W^{(1)} = \{ 5, 6 \}$ ($w^{(1)} = 5$), and $W^{(2)} = \{ 3, 4, 7 \}$ ($w^{(2)} = 3$). Inequality $x_3 + x_4 + x_7 \leq 1$ is violated by $\bar x$ since $\bar x_3 + \bar x_4 + \bar x_7 = 1.5$. Removing edge $(4, 7)$ from $G^{(2)}$ creates a stable set of size 2, and~\eqref{eq:lemmalambda} gives $\lambda^{(2)} = -1$, as expected. Thus,~\eqref{eq:lifted} results in
\begin{equation}
x_3 + x_4 + x_5 + x_6 + x_7 \leq 2,
\label{eq:ineqexample}
\end{equation}
which is valid for $STAB(G^{(1)})$ and violated by $\bar x$. The clique-lifting of~\eqref{eq:ineqexample} with Lemma~\ref{lem:aproxlambda} gives $\lambda^{(1)} = 0$.

In the general case, a nonempty intersection of $W^{(i-1)}$ and $W^{(i)}$ leads to an inequality with coefficients greater than 1. This is the case in the example of Figure~\ref{fig:graph}.

\section{Separation heuristic}

A separation heuristic consists of the generation of at most $MAXITER$ sequences of cliques. For each sequence $\langle W^{(0)}, \ldots, W^{(k)} \rangle$, the following steps are performed: \\ \\
\textbf{Finding $\mathbf{W^{(0)}}$:} the subset $W^{(0)}$ is a clique of $G$, maximal with respect to two properties, namely:
  \begin{enumerate}
    \item Its size $|W^{(0)}|$ is at most $MAXCLIQUESZ$.
    \item Its weight, computed as $\sum_{v \in W^{(0)}} \bar x_v$, is at least
    \begin{displaymath}
     \max \{ THRESHOLD, THRESHOLDPERVERTEX \times |W^{(0)}| \}.
     \end{displaymath}
    \label{it:minweight}
  \end{enumerate}
The (at most) $MAXITER$ cliques are generated with a greedy backtracking enumeration in $G$. In this enumeration, vertices are considered in a nondecreasing order of their values in $\bar x$. The parameter $MAXENUMCLIQUE$ establishes the maximum number of maximal cliques violating property~\ref{it:minweight} that can be enumerated before stopping the enumeration. The enumerated cliques may be disjoint (and thus giving rise to rank inequalities) or have pairwise non-empty intersection. Note that if $MAXCLIQUESZ = 2$, then we are generating \emph{edges} and performing thus an edge projection.
    
Every $W^{(0)}$ generated is a clique of $G$. Then, if the weight $\sum_{v\in W^{(0)}} \bar x_v$ is at least $CLIQUEINEATHRESHOLD$, then it is extended to a maximal clique of $G$. In addition, if the associated clique inequality is violated, then it is considered as a cut.

\textbf{Finding $\mathbf{W^{(i)}, i > 0}$:} $W^{(i)}$ is a maximal clique of $G^{(i)}$ with size at most $MAXCLIQUESZ$. In order to avoid sequences leading to the same inequality, $W^{(i)}$ must contain either the endpoints of a false edge in $F^{(i-1)}$ or, if the elements of $F^{(i-1)}$ do not generate any false edge, $v$ such that $x_v = \max \{ w_w \mid w \in \cup_{j = \max \{ 0, i-J \}}^{i-1} W^{(j)}$, where $J$ is the maximum value such that $V\setminus \cup_{j = i-J}^{i-1} W^{(j)} \ne \emptyset$.

\begin{algorithm}
\caption{Maximal-clique based heuristic}
\label{alg:cliqueheu}
\begin{algorithmic}[1]
\State Find maximal clique $W$, not violated by $x$
\State $F \gets \emptyset$
\For {$u \in V \setminus W$}
   	\ForAll {$v \in \cap_{w \in W \setminus N(u)} (N(w) \setminus W)$}
   		\State $F \gets F + uv$
   	\EndFor
\EndFor
\State $E \gets E \cup F$
\State Let $X = \langle v_1, v_2, \ldots, v_\ell \rangle$ be a nonicreasing
order of $x_{v_i}$ of all nonnull valued vertices
\For {$i \gets 1, 2, \ldots, \ell$}
	\State Find a maximal clique containing $v_i$
	\If {corresponding clique inequality is violated}
		\State Lift false edges
	\EndIf
\EndFor
\end{algorithmic}
\end{algorithm}

% \section{Branching Procedure}
% 
% The branching procedure acts on a fractional solution $\bar x$ of a subproblem
% $\sigma$  and generates one or two new subproblems. The first step is to search
% for a vertex $v$ with the following two properties:
% \begin{enumerate}
%   \item $1 > \bar x_v > 0$; and
%   \label{it:xfract}
%   \item there exits $u \in V$, $u < v$, such that either 
%   \begin{enumerate}
%     \item $N[u] \cap \bar N(v) =
%   \emptyset$; or 
%   \label{it:dominated}
%   \item $\sum_{w \in N[u] \cap \bar N(v)} \bar x_w < 1$.
%   \label{it:elimsym}
%   \end{enumerate}
%   \label{it:symmetry}
% \end{enumerate}
% If such $u$ and $v$ are found, then the number of new subproblems depends on
% property~\ref{it:symmetry}. If~\ref{it:dominated} is valid, then only one
% subproblem is generated by adding the equality $x_v = 0$ to $\sigma$. Observe
% that in this case $uv \in E$ and, in addition, for every stable set $S$
% containing $v$, $S - v + u$ is also a stable set since $u$ is dominated by $v$. The second
% case occurs when~\ref{it:dominated} is not valid but~\ref{it:elimsym} is. In
% this case, two subproblems, denoted as $\sigma_0$ and $\sigma_{>1}$, are
% generated. Subproblem $\sigma_{>1}$ is obtained from $\sigma$ by the addition of
% inequality $\sum_{w \in N[u] \cap \bar N(v)} x_w \geq 1$. On the other hand,
% $\sigma_0$ derives from $\sigma$ with the two additional equalities $\sum_{w \in
% N[u] \cap \bar N(v)} x_w = 0$ and $x_v = 0$. One remark on this procedure is
% that all stable sets of $G$ containing $v$ and none of the vertices in $N[u]
% \cap \bar N(v)$ are eliminated. This is because such a stable set
% $S$ implies that $S - v + u$ is also a stable set of $G$.
% 
% When several pairs $u, v$ satisfy~\ref{it:xfract} and~\ref{it:symmetry}, the
% choice of $v$ is for the one with the largest $\bar x_v$. Then, $u$ is chosen
% such that $\sum_{w \in N[u] \cap \bar N(v)} \bar x_w$ is as small as possible.
% Otherwise, if there is no pair $u, v$ satisfying~\ref{it:xfract}
% and~\ref{it:symmetry}, then we chose the most fractional $\bar x_v$ and generate
% two new subproblems by fixing $x_v$ to zero or one, respectively.

\section{Preliminary computational experiments}

In this section we provide preliminary computational experiments in order to
explore whether the proposed method is useful as a cut-generating tool or not. Our main goal is not to provide a competitive algorithm for MSS, since combinatorial algorithms are much more effective than cutting-plane algorithms for this problem. Anyway, we intend to assess whether the proposed procedure is effective at generating generalized rank cuts for the MSS polytope, and the nature of the obtained cuts.

To this end, we implemented the cut-generating procedure as a separation
procedure attached to \textsc{Cplex} 12.6's branch and cut algorithm to compute
a strengthened upper bound for the root subproblem. Whenever a fractional
solution is found, we execute the cut-generating procedure several times, each execution starting from a different clique. In order to ensure that the initial cliques are not repeated, we employ a backtracking-based enumeration that in principle enumerates all cliques in the graph. We employ for this purpose \"Ostergaard's algorithm in \cite{Ostergard.01}. We do not generate all cliques, but stop when a prespecified number of initial cliques is found instead.

For each initial clique, we generate a sequence of cliques with a greedy algorithm that tries not to repeat too many vertices already belonging to a clique in the sequence. We project each clique in the sequence, until a simple greedy heuristic finds a violated clique inequality. When this happens, we apply the clique-lifting procedure and check if the generated inequality (which is guaranteed to be valid) is violated.

The initial model contains only the constraint $x_i + x_j \le 1$ for every edge
$ij\in E$. We implement a simple greedy heuristic for calculating a lower bound
at the root note in the enumeration tree. We also implement the heuristic in Lemma~\ref{lem:upalphac} for calculating a dual bound for $\lambda$ within the cut-generating procedure. We first search for rank inequalities (by projecting at each step a clique disjoint to the preceding cliques), which include clique inequalities. If such inequalities are not found, then we allow for projecting cliques with nonempty intersection with the preceding cliques, hence generalized rank inequalities can be obtained in this case. The size $s\in\mathbb{Z}_+$ of the analyzed cliques is a parameter of our implementation, and we try with $2\le s\le 7$ in the experiments. 
In addition to the separation procedure, we also implemented the rounding
heuristic proposed in~\cite{Pardalos} and employed it to compute lower bounds.

Table~\ref{tab:resultsDIMACS} summarizes the preliminary experiments with some
instances from the DIMACS benchmark and for random graphs with 100 vertices
(last two rows).
The notation $G(n,d)$ specifies random graphs with $n$ vertices and a density of
$d\in[0,1]$, and for these instances we report the average results over five
randomly-generated instances. The experiments were performed on a 32-bit
personal computer, with a time limit of five minutes. The preprocessing, cut
generation, and variable fixing procedures from \textsc{Cplex} are turned off.

Following the approach used in \cite{Rossi.Smriglio.01}, for each graph we
choose the best parameters and report the obtained results. The first four
columns contain the instance name, the number of vertices, the graph density,
and its stability number. The following three columns contain data for the root
note in the enumeration tree: the column ``LB'' contains the lower bound found
by the rounding heuristic, the column ``UB'' contains the upper bound after the
last successful execution of the cut-generating procedure, and the column ``Time'' reports the total time spent at the root node, in seconds. The cells marked with $***$ specify that the computation has been aborted at the time limit. The columns UB\cite{Rossi.Smriglio.01} and UB\cite{Pardalos} contain the best upper bound attained in \cite{Rossi.Smriglio.01} and \cite{Pardalos}, respectively. Finally, the last three columns contain the number of generated clique cuts, violated rank inequalities, and violated generalized rank inequalities, respectively.

As Table~\ref{tab:resultsDIMACS} shows, the procedure is able to generate a
large number of cuts, and provides upper bounds that are competitive with those
generated in \cite{Pardalos} and \cite{Rossi.Smriglio.01} for a representative
sample of benchmark graphs.
Similarly to existing procedures, out cut-genereating algorithm finds a large
number of violated clique inequalities, and is also able to find many violated
rank inequalities. The number of generalized rank inequalities generated by the
procedure is smaller, but nevertheless provides an interesting set of additional
and non-trivial valid inequalities. As a future work, we intend to perform
extensive computational experiments with the proposed cut generating procedure
in a full branch and cut algorithm.

\begin{table*}
\centering
{\scriptsize
\begin{tabular}{ccccccccccccccc} 
\hline
%Encabezado fila 1
\multicolumn{3}{l}{Instances} & $D$ & \multicolumn{4}{l}{Root subproblem} &
\quad & \multicolumn{2}{l}{Time (sec.)} &\quad &  \multicolumn{2}{l}{Number of
cuts} \\ \cline{1-3} \cline{5-8} \cline{10-11} \cline{13-14}
%Encabezado fila 2
$G=(V,E)$ & $|V|$/Dens. & $\alpha(G)$ && LB & \multicolumn{3}{l}{UB per type of
cuts} && W-Rank & Clique && W-Rank & Clique \\ \cline{6-8}
%Encabezado fila 3
&&&&& W-Rank & Clique & \cite{Pardalos} &&& cuts only\\ \hline \hline
%Datos
\input{resultados1.0-dimacs.tex}
\hline \hline
\input{resultados1.0-rand.tex}
 \hline
\end{tabular}}
\label{tab:resultsDIMACS}
\medskip
\caption{Version 1.0: Results with graphs selected from the DIMACS benchmark and
with random graphs.}
\end{table*}

\begin{table*}
\centering
{\scriptsize
\begin{tabular}{ccccccccccccccc} \hline
%Encabezado fila 1
\multicolumn{3}{l}{Instances} & $D$ & \multicolumn{4}{l}{Root subproblem} & \quad & \multicolumn{2}{l}{Time (sec.)} & \quad & \multicolumn{2}{l}{Number of cuts} \\ \cline{1-3} \cline{5-8} \cline{10-11} \cline{13-14}
%Encabezado fila 2
$G=(V,E)$ & $|V|$/Dens. & $\alpha(G)$ && LB & \multicolumn{3}{l}{UB per type of cuts} && Clique $+$ & Clique && Rank/W & Clique \\ \cline{6-8}
%Encabezado fila 3
&&&&& Rank/W & Clique & \cite{Pardalos} && Rank/W cuts & cuts only\\ \hline
\hline
%Datos
\input{resultados2.0-dimacs.tex}
\hline \hline
\input{resultados2.0-rand.tex}
 \hline
\end{tabular}}
\label{tab:resultsDIMACS}
\medskip
\caption{Version 2.0: Results with graphs selected from the DIMACS benchmark and
with random graphs.}
\end{table*}

\section{Conclusions}

In this work we have presented a general cut-generating procedure for the standard formulation of the maximum stable set polytope, which is able to generate both violated rank and generalized rank inequalities. The main objective of this algorithm is to generalize existing procedures based on edge projection, and employs a lifting procedure in order to construct general valid inequalities from an initial clique inequality by undoing the operation of clique projection in the original graph. The computational experiments presented in this work are of a preliminary nature, and show that the proposed procedure is effective at generating general cuts, and may be competitive in a general setting.

\bibliographystyle{plain}
\bibliography{./stab}

\end{document}

